package com.paic.du.lib.sort;

public class QuickSort {

	public static void swap (int []ori, int i, int j){
		int m=ori[i];
		ori[i]=ori[j];
		ori[j]=m;
	}
	public static int partition(int [] ori, int _left, int _right){
		int index;
		int tmp=ori[_right];
		for(int i=index=_left;i<_right;i++){
			if(ori[i]<tmp)
			swap(ori, index++, i);
		}
		swap(ori, index, _right);
		return index;
	}
	
	public static void quickSort(int [] ori, int i, int j){
		if(i<j){
			int split=partition(ori, i, j);
			quickSort(ori, i, split-1);
			quickSort(ori, split+1, j);
		}
	}
	
	public static void main(String args[]){
		int []m={1,2,4,5,6,4,3,2};
		quickSort(m, 0, m.length-1);
	}
}
